package com.chj.jz.dp.class04;

// https://www.lintcode.com/problem/perfect-squares/description
public class Code01_PerfectSquares {
	/**
     * @param n: a positive integer
     * @return: An integer
     */
    public static int numSquares(int n) {
        // write your code here
    	
    	int[] f = new int[n + 1];
    	f[0] = 0;
    	int i, j;
    	for(i = 1; i <= n; i++) {
    		f[i] = Integer.MAX_VALUE;
    		for(j = 1; j * j <= i; j++) {
    			if(f[i - j * j] != Integer.MAX_VALUE) {
    				f[i] = Math.min(f[i], f[i - j * j] + 1);
    			}
    		}
    	}
    	
    	return f[n];
    }
    
    public static void main(String[] args) {
		{
			System.out.println(numSquares(12));
		}
		{
         	System.out.println(numSquares(13));
		}
	}

}
